DataBase as a Service (hereinafter referred to as “DBaaS”) is a service for users to store their data into an external database (DataBase, herein after abbreviated as “DB”). As services for users to use external computing resources, such as cloud computing, come into widespread use, it is to be expected that DBaaS will become widely used.
DBaaS has the function for searching desired information in data (information) stored in a DB. A user uses the function to retrieve desired information on the basis of information stored in the DB. In this case, DBaaS executes a search instruction for extracting information desired by a user in response to DBaaS receiving the search instruction (query) sent from the user. Then, DBaaS sends the extracted information to the user.
However, the types of possible search instructions of DB may be limited. For example, if a DB uses an encryption scheme such as “searchable encryption” (for example, if the DB is an “encrypted database” as exemplified in NPL 1 and NPL 2), the types of possible search instructions of the DB are limited.
The searchable encryption is a technique that enables searches without decrypting encrypted information (encrypted text). For example, the searchable encryption enables a searching process based on encrypted information in response to a search instruction while maintaining confidentiality of the information to be searched by using cipher.
For example, NPL 3 discloses an example of searchable encryption called encryption with keyword search. In the encryption with keyword search, determination is made as to whether encrypted information is equal to a given value without decrypting the information.
Further, NPL 4 discloses one example of searchable encryption called order-preserving encryption, for example. In the order-preserving encryption, determination is made as to whether encrypted information satisfies criteria without decrypting the information.
Order-preserving encryption will now be described. An encrypted text by encrypting an unencrypted value x with a private key K is denoted as E(K, x). Note that the encrypted text E(K, x) is, for example, an integer value in accordance with the order-preserving encryption.
In this case, the necessary and sufficient condition of an unencrypted value “a” being greater than an unencrypted value “b” in the order-preserving encryption is that the value of an encrypted text E(K, a) is greater than the value of an encrypted text E(K, b). Accordingly, that “the value of E(K, a) is greater than the value of E(K, b)” represents that “the value of E(K, a) as an integer value is greater than the value of E(K, b)”.
For example, an unencrypted value “a” is encrypted to an encrypted text E(K, a) with a private key K. The encrypted DB receives a search instruction, for example, “retrieve all pieces of information satisfying search criteria ‘greater than or equal to the value of E(K, a)’”. The database extracts information in accordance with the received search instruction. In this case, the information is encrypted. Accordingly, desired information is generated by decrypting information extracted by the database.
An encrypted DB is one example of DBaaS and is a secure DB which is implemented by using searchable encryption. The encrypted DB stores information encrypted in accordance with searchable encryption. The encrypted DB receives search instructions written by encrypted search criteria in accordance with the searchable encryption and extracts information in accordance with the search instructions without decrypting the information.
However, the types of possible search instructions of an encrypted DB may be limited. For example, in an encrypted DB employing the match search encryption disclosed in NPL 3, the only type of possible search instructions without decryption is a search instruction for searching based on “whether encrypted information is equal to a given value”. Further, in an encrypted DB employing the order-preserving encryption disclosed in NPL 4, the only type of possible search instructions without decryption is a search instruction for searching based on “whether encrypted information is greater than or equal to a given value”.
Of course, an encrypted DB can decrypt encrypted information with a private key for the encryption and can make a search by using the decrypted information. However, it is undesirable for security reasons that the encrypted DB includes information about a private key for encryption. Therefore, most encrypted DBs employ a configuration that the encrypted DBs do not include information about private keys for encryption. In such a configuration, encrypted information stored in the encrypted DB cannot be decrypted, the types of possible search instructions of the encrypted DB are limited.
PTL 1 discloses one example of a database encryption system where information to be stored is encrypted and different encryption schemes are used even for the same encrypted information. The database encryption system extracts information in accordance with an instruction to make a match search as in the encrypted DB described above. However, according to the database encryption system, extractable information is limited.